class DSU():
    def __init__(self):
        self.parent = {}

    def find(self, node):
        if node not in self.parent:
            self.parent[node] = node
        if self.parent[node] == node:
            return node
        else:
            parent = self.find(self.parent[node])
            self.parent[node] = parent

            return parent

    def union(self, x, y):
        if x == y:
            return
        px = self.find(x)
        py = self.find(y)

        self.parent[py] = px


class Solution:
    def longestConsecutive(self, nums: list) -> int:
        dsu = DSU()
        for num in nums:
            dsu.union(num, num + 1)
        cache = {}
        res = 0
        for num in set(nums):
            p = dsu.find(num)
            if p in cache:
                cache[p] += 1
            else:
                cache[p] = 1
            res = max(res, cache[p])

        return res


if __name__ == "__main__":
    print(Solution().longestConsecutive([100, 4, 200, 1, 3, 2]))
